Systems that process electronic transactions frequently use passwords to authenticate a party wishing to access resources via those transactions. For example, an online bank requires that its customers log in using an identifier and password. Such systems typically store these passwords in a secure database; when a user attempts to log into an account of the online bank, the bank retrieves the password corresponding to the user identifier and compares the password to that submitted by the user.
Many such systems store these passwords in plain text in the database. Nevertheless, all accounts could be compromised if an attacker managed to obtain a copy of this password database. To improve security, some systems store a secure hash (a one-way function) of each password instead of the plain text. In this way, an attacker will not have the passwords even if she gains hold of the database.
That said, while an attacker in possession of the password database does not have the passwords, she is at liberty to make repeated guesses until an account is compromised. The more accounts in the password database, the greater the probability that one of the accounts has a weak password. When all passwords are hashed using the same one-way function, an attacker can reduce the computational effort required to compromise one of many accounts by generating a list of pre-hashed guesses—known as a “rainbow table”—and finding the intersection of the hashed guesses and the hashed passwords. To mitigate the effectiveness of rainbow tables, some other systems then store passwords using a salted hash, which requires an attacker to re-hash each guess for each account.
Nevertheless, while such salted hashes increases the computational effort required for an attacker to compromise an account, they do not eliminate the problem of attackers being able to guess weak passwords within a database. To further improve security, some systems mathematically split each password hash into two pieces of data (“shares”), such that each share on its own conveys no information about the original password hash. These systems store each share in a different database that may be in a different physical location and protected by different security measures. A successful attack would require that the attacker steal both databases. For this technique to be secure, a system implementing it satisfies the following:
1. There are three distinct systems, preferably running on distinct hardware:                a. The system that is running the client application that is utilizing the password storage and authentication service, such as an online banking system. “Client” is the networking term, as in “client/server”.        b. A server that is running one half of the password storage and authentication service with the database that contains one of the shares for each account (the “red” server).        c. A server that is running the other half of the password storage and authentication service with the database that contains the other share for each account (the “blue” server).        
2. When storing or authenticating a password, the client application splits the password and sends one share to each of the servers and neither of the servers is ever in possession of both password shares or the original password or password hash.
3. The password typed by the user and the corresponding password hash exists ephemerally on the system that is running the client application when a password is either stored or authenticated.
4. Authentication is done cooperatively using an algorithm that does not require the password hash to be reassembled from the two shares at any time or in any location.
It should be understood that this split-password approach is still vulnerable to attack if an attacker has sufficient time to eventually compromise both the red and blue servers. As a final improvement, if an attacker has stolen one of the databases, it is possible to update all the shares on both servers in a way that renders the stolen database useless to the attacker. Such an improvement involves having the red and blue servers agree on a random value and then apply that value to all the shares, creating a new version of each share; this process has the advantage of not needing to reassemble password hashes. Such a process is called “proactivization,” and, if performed regularly, it reduces the time window during which an attacker must compromise both servers to achieve a successful attack.
It should be understood that proactivization can be a complex process which must take certain practical considerations into account. For example, such a proactivization process may take a long time because each password entry must be modified in both databases. Also, the password storage and authentication operations must remain available during such a proactivization process. Further, the red and blue servers must work as independently as possible in order to maintain the security of the system. Finally, for an authentication operation to succeed, the red and blue servers must use the same version of the two shares corresponding to the password being authenticated.
The above-described proactive approach to updating secret shares involves synchronization between the red and blue servers. Conventional approaches to proactively updating secret shares for secrets such as passwords involve replacing, by one of the servers, each current share in that server's database with a new share; this replacement is performed synchronously with that of the other server. In this way, each server computes the new version of the share, erases the current version of the share, and stores the new version.